package com.promote.algorithm;

/**
 * @ClassName FindDiagonalOrder
 * Description 对角线遍历
 * @Author LiZiHao
 * Date 2022/12/8 13:40
 * @Version 1.0
 **/
public class FindDiagonalOrder {

    /**
     * （1）先得出遍历的次数，也就是对角线的条数为i=n+m-1，所以数组遍历条件也就是i<n+m-1。
     * （2）在看图，对角线上的每个元素坐标之和为i,也就是元素的坐标xy与i的关系为：x+y=i
     * （3）如何遍历？看图中，偶数对应的对角线上的元素是从下往上遍历，而奇数对应的对角线上的元素是从上往下遍历，那么只要确定遍历的起始点和结束点就好啦！我们先看偶数对角线的起点和终点，因为奇数对角线和它相反，知道了偶数的，也不难得出奇数的的。
     *
     * 当i<n-1时，起始点坐标x=i，如1的x坐标为0，i也为0,结束点的横坐标x=0
     * 当i>=n-1时，起始点坐标x=n-1,如2的x坐标为2，i也为2,结束点的纵坐标y=m-1,根据（2）中的关系式,所以得出横坐标x=i-(m-1)
     * 所以偶数对角线遍历时起始点的x的坐标为min(i,n-1)，结束点的x坐标为max(0,i-(m-1)),而坐标y就是i-x
     *

     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {

        int n = mat.length;
        int m = mat[0].length;
        int[] result = new int[n*m];

        for (int i = 0,idx = 0; i < n+m-1; i++) {
            //偶数对角线，从下往上遍历
            if (i%2 == 0) {
                for (int x = Math.min(i,n-1); x>=Math.max(0,i-m+1);x--) {
                    result[idx++] = mat[x][i-x];
                }
            } else{
                for (int x = Math.max(0,i-m+1); x<=Math.min(i,n-1);x++) {
                    result[idx++] = mat[x][i-x];
                }
            }
        }
        return result;

    }


}
